/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-23-合并k个升序链表
 * @date 2025/4/21 15:15
 */
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left > right)
            return null;
        if (left == right)
            return lists[left];
        // 分治法
        int mid = (left + right) >> 1;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    private ListNode mergeTwoLists(ListNode p, ListNode q) {
        if (p == null || q == null) {
            // 这个if写的好啊好啊
            return p != null ? p : q;
        }
        ListNode head = new ListNode(1);
        ListNode temp = head;
        while (p != null && q != null) {
            if (p.val < q.val) {
                temp.next = p;
                p = p.next;
            } else {
                temp.next = q;
                q = q.next;
            }
            temp = temp.next;
        }
        temp.next = (p != null ? p : q); // 这个三元表达式写得好！
        return head.next;
    }
}